<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.9.1"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Eigen: Solving Sparse Linear Systems</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
  $(document).ready(function() { init_search(); });
/* @license-end */
</script>
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
    jax: ["input/TeX","output/HTML-CSS"],
});
</script>
<script type="text/javascript" async="async" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="eigendoxy.css" rel="stylesheet" type="text/css">
<!--  -->
<script type="text/javascript" src="eigen_navtree_hacks.js"></script>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectlogo"><img alt="Logo" src="Eigen_Silly_Professor_64x64.png"/></td>
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname"><a href="http://eigen.tuxfamily.org">Eigen</a>
   &#160;<span id="projectnumber">3.4.90 (git rev 67eeba6e720c5745abc77ae6c92ce0a44aa7b7ae)</span>
   </div>
  </td>
   <td>        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.svg"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.svg" alt=""/></a>
          </span>
        </div>
</td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.9.1 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
var searchBox = new SearchBox("searchBox", "search",false,'Search','.html');
/* @license-end */
</script>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&amp;dn=gpl-2.0.txt GPL-v2 */
$(document).ready(function(){initNavTree('group__TopicSparseSystems.html',''); initResizable(); });
/* @license-end */
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">Solving Sparse Linear Systems<div class="ingroups"><a class="el" href="group__Sparse__chapter.html">Sparse linear algebra</a></div></div>  </div>
</div><!--header-->
<div class="contents">
<p>In <a class="el" href="namespaceEigen.html" title="Namespace containing all symbols from the Eigen library.">Eigen</a>, there are several methods available to solve linear systems when the coefficient matrix is sparse. Because of the special representation of this class of matrices, special care should be taken in order to get a good performance. See <a class="el" href="group__TutorialSparse.html">Sparse matrix manipulations</a> for a detailed introduction about sparse matrices in <a class="el" href="namespaceEigen.html" title="Namespace containing all symbols from the Eigen library.">Eigen</a>. This page lists the sparse solvers available in <a class="el" href="namespaceEigen.html" title="Namespace containing all symbols from the Eigen library.">Eigen</a>. The main steps that are common to all these linear solvers are introduced as well. Depending on the properties of the matrix, the desired accuracy, the end-user is able to tune those steps in order to improve the performance of its code. Note that it is not required to know deeply what's hiding behind these steps: the last section presents a benchmark routine that can be easily used to get an insight on the performance of all the available solvers.</p>
<h1><a class="anchor" id="TutorialSparseSolverList"></a>
List of sparse solvers</h1>
<p>Eigen currently provides a wide set of built-in solvers, as well as wrappers to external solver libraries. They are summarized in the following tables:</p>
<h2><a class="anchor" id="TutorialSparseSolverList_Direct"></a>
Built-in direct solvers</h2>
<table class="manual">
<tr>
<th>Class</th><th>Solver kind</th><th><a class="el" href="classEigen_1_1Matrix.html" title="The matrix class, also used for vectors and row-vectors.">Matrix</a> kind</th><th>Features related to performance </th><th class="width20em"><p class="starttd"></p>
<p class="intertd">Notes</p>
<p class="intertd"></p>
<p class="endtd"></p>
</th></tr>
<tr>
<td><a class="el" href="classEigen_1_1SimplicialLLT.html" title="A direct sparse LLT Cholesky factorizations.">SimplicialLLT</a> <br  />
 <code>#include&lt;Eigen/<a class="el" href="group__SparseCholesky__Module.html">SparseCholesky</a>&gt;</code></td><td>Direct LLt factorization</td><td>SPD</td><td>Fill-in reducing </td><td><p class="starttd"><a class="el" href="classEigen_1_1SimplicialLDLT.html" title="A direct sparse LDLT Cholesky factorizations without square root.">SimplicialLDLT</a> is often preferable</p>
<p class="endtd"></p>
</td></tr>
<tr>
<td><a class="el" href="classEigen_1_1SimplicialLDLT.html" title="A direct sparse LDLT Cholesky factorizations without square root.">SimplicialLDLT</a> <br  />
 <code>#include&lt;Eigen/<a class="el" href="group__SparseCholesky__Module.html">SparseCholesky</a>&gt;</code></td><td>Direct LDLt factorization</td><td>SPD</td><td>Fill-in reducing </td><td><p class="starttd">Recommended for very sparse and not too large problems (e.g., 2D Poisson eq.)</p>
<p class="endtd"></p>
</td></tr>
<tr>
<td><a class="el" href="classEigen_1_1SparseLU.html" title="Sparse supernodal LU factorization for general matrices.">SparseLU</a> <br  />
 <code>#include&lt;Eigen/<a class="el" href="group__SparseLU__Module.html">SparseLU</a>&gt;</code> </td><td>LU factorization  </td><td>Square </td><td>Fill-in reducing, Leverage fast dense algebra </td><td><p class="starttd">optimized for small and large problems with irregular patterns </p>
<p class="endtd"></p>
</td></tr>
<tr>
<td><a class="el" href="classEigen_1_1SparseQR.html" title="Sparse left-looking QR factorization with numerical column pivoting.">SparseQR</a> <br  />
 <code>#include&lt;Eigen/<a class="el" href="group__SparseQR__Module.html">SparseQR</a>&gt;</code> </td><td>QR factorization </td><td>Any, rectangular</td><td>Fill-in reducing </td><td>recommended for least-square problems, has a basic rank-revealing feature </td></tr>
</table>
<h2><a class="anchor" id="TutorialSparseSolverList_Iterative"></a>
Built-in iterative solvers</h2>
<table class="manual">
<tr>
<th>Class</th><th>Solver kind</th><th><a class="el" href="classEigen_1_1Matrix.html" title="The matrix class, also used for vectors and row-vectors.">Matrix</a> kind</th><th>Supported preconditioners, [default] </th><th class="width20em"><p class="starttd"></p>
<p class="intertd">Notes</p>
<p class="intertd"></p>
<p class="endtd"></p>
</th></tr>
<tr>
<td><a class="el" href="classEigen_1_1ConjugateGradient.html" title="A conjugate gradient solver for sparse (or dense) self-adjoint problems.">ConjugateGradient</a> <br  />
 <code>#include&lt;Eigen/<a class="el" href="group__IterativeLinearSolvers__Module.html">IterativeLinearSolvers</a>&gt;</code> </td><td>Classic iterative CG</td><td>SPD </td><td><a class="el" href="classEigen_1_1IdentityPreconditioner.html" title="A naive preconditioner which approximates any matrix as the identity matrix.">IdentityPreconditioner</a>, [<a class="el" href="classEigen_1_1DiagonalPreconditioner.html" title="A preconditioner based on the digonal entries.">DiagonalPreconditioner</a>], <a class="el" href="classEigen_1_1IncompleteCholesky.html" title="Modified Incomplete Cholesky with dual threshold.">IncompleteCholesky</a> </td><td><p class="starttd">Recommended for large symmetric problems (e.g., 3D Poisson eq.)</p>
<p class="endtd"></p>
</td></tr>
<tr>
<td><a class="el" href="classEigen_1_1LeastSquaresConjugateGradient.html" title="A conjugate gradient solver for sparse (or dense) least-square problems.">LeastSquaresConjugateGradient</a> <br  />
 <code>#include&lt;Eigen/<a class="el" href="group__IterativeLinearSolvers__Module.html">IterativeLinearSolvers</a>&gt;</code></td><td>CG for rectangular least-square problem</td><td>Rectangular </td><td><a class="el" href="classEigen_1_1IdentityPreconditioner.html" title="A naive preconditioner which approximates any matrix as the identity matrix.">IdentityPreconditioner</a>, [<a class="el" href="classEigen_1_1LeastSquareDiagonalPreconditioner.html" title="Jacobi preconditioner for LeastSquaresConjugateGradient.">LeastSquareDiagonalPreconditioner</a>] </td><td><p class="starttd"><a class="el" href="classEigen_1_1Solve.html" title="Pseudo expression representing a solving operation.">Solve</a> for min |Ax-b|^2 without forming A'A</p>
<p class="endtd"></p>
</td></tr>
<tr>
<td><a class="el" href="classEigen_1_1BiCGSTAB.html" title="A bi conjugate gradient stabilized solver for sparse square problems.">BiCGSTAB</a> <br  />
 <code>#include&lt;Eigen/<a class="el" href="group__IterativeLinearSolvers__Module.html">IterativeLinearSolvers</a>&gt;</code></td><td>Iterative stabilized bi-conjugate gradient</td><td>Square </td><td><a class="el" href="classEigen_1_1IdentityPreconditioner.html" title="A naive preconditioner which approximates any matrix as the identity matrix.">IdentityPreconditioner</a>, [<a class="el" href="classEigen_1_1DiagonalPreconditioner.html" title="A preconditioner based on the digonal entries.">DiagonalPreconditioner</a>], <a class="el" href="classEigen_1_1IncompleteLUT.html" title="Incomplete LU factorization with dual-threshold strategy.">IncompleteLUT</a> </td><td>To speedup the convergence, try it with the <a class="el" href="classEigen_1_1IncompleteLUT.html">IncompleteLUT</a> preconditioner. </td></tr>
</table>
<h2><a class="anchor" id="TutorialSparseSolverList_Wrapper"></a>
Wrappers to external solvers</h2>
<table class="manual">
<tr>
<th>Class</th><th>Module</th><th>Solver kind</th><th><a class="el" href="classEigen_1_1Matrix.html" title="The matrix class, also used for vectors and row-vectors.">Matrix</a> kind</th><th>Features related to performance </th><th>Dependencies,License</th><th class="width20em"><p class="starttd"></p>
<p class="intertd">Notes</p>
<p class="endtd"></p>
</th></tr>
<tr>
<td><a class="el" href="classEigen_1_1PastixLLT.html" title="A sparse direct supernodal Cholesky (LLT) factorization and solver based on the PaStiX library.">PastixLLT</a> <br  />
 <a class="el" href="classEigen_1_1PastixLDLT.html" title="A sparse direct supernodal Cholesky (LLT) factorization and solver based on the PaStiX library.">PastixLDLT</a> <br  />
 <a class="el" href="classEigen_1_1PastixLU.html" title="Interface to the PaStix solver.">PastixLU</a></td><td><a class="el" href="group__PaStiXSupport__Module.html">PaStiXSupport </a></td><td>Direct LLt, LDLt, LU factorizations</td><td>SPD <br  />
 SPD <br  />
 Square</td><td>Fill-in reducing, Leverage fast dense algebra, Multithreading </td><td>Requires the <a href="http://pastix.gforge.inria.fr">PaStiX</a> package, <b>CeCILL-C</b>  </td><td>optimized for tough problems and symmetric patterns </td></tr>
<tr>
<td><a class="el" href="classEigen_1_1CholmodSupernodalLLT.html" title="A supernodal Cholesky (LLT) factorization and solver based on Cholmod.">CholmodSupernodalLLT</a></td><td><a class="el" href="group__CholmodSupport__Module.html">CholmodSupport </a></td><td>Direct LLt factorization</td><td>SPD</td><td>Fill-in reducing, Leverage fast dense algebra </td><td>Requires the <a href="http://www.suitesparse.com">SuiteSparse</a> package, <b>GPL</b>  </td><td></td></tr>
<tr>
<td><a class="el" href="classEigen_1_1UmfPackLU.html" title="A sparse LU factorization and solver based on UmfPack.">UmfPackLU</a></td><td><a class="el" href="group__UmfPackSupport__Module.html">UmfPackSupport </a></td><td>Direct LU factorization</td><td>Square</td><td>Fill-in reducing, Leverage fast dense algebra </td><td>Requires the <a href="http://www.suitesparse.com">SuiteSparse</a> package, <b>GPL</b>  </td><td></td></tr>
<tr>
<td>KLU</td><td><a class="el" href="group__KLUSupport__Module.html">KLUSupport </a></td><td>Direct LU factorization</td><td>Square</td><td>Fill-in reducing, suitted for circuit simulation </td><td>Requires the <a href="http://www.suitesparse.com">SuiteSparse</a> package, <b>GPL</b>  </td><td></td></tr>
<tr>
<td><a class="el" href="classEigen_1_1SuperLU.html" title="A sparse direct LU factorization and solver based on the SuperLU library.">SuperLU</a></td><td><a class="el" href="group__SuperLUSupport__Module.html">SuperLUSupport </a></td><td>Direct LU factorization</td><td>Square</td><td>Fill-in reducing, Leverage fast dense algebra </td><td>Requires the <a href="http://crd-legacy.lbl.gov/~xiaoye/SuperLU/">SuperLU</a> library, (BSD-like) </td><td></td></tr>
<tr>
<td><a class="el" href="classEigen_1_1SPQR.html" title="Sparse QR factorization based on SuiteSparseQR library.">SPQR</a></td><td><a class="el" href="group__SPQRSupport__Module.html">SPQRSupport </a>  </td><td>QR factorization  </td><td>Any, rectangular</td><td>fill-in reducing, multithreaded, fast dense algebra </td><td>requires the <a href="http://www.suitesparse.com">SuiteSparse</a> package, <b>GPL</b> </td><td>recommended for linear least-squares problems, has a rank-revealing feature </td></tr>
<tr>
<td><a class="el" href="classEigen_1_1PardisoLLT.html" title="A sparse direct Cholesky (LLT) factorization and solver based on the PARDISO library.">PardisoLLT</a> <br  />
 <a class="el" href="classEigen_1_1PardisoLDLT.html" title="A sparse direct Cholesky (LDLT) factorization and solver based on the PARDISO library.">PardisoLDLT</a> <br  />
 <a class="el" href="classEigen_1_1PardisoLU.html" title="A sparse direct LU factorization and solver based on the PARDISO library.">PardisoLU</a></td><td><a class="el" href="group__PardisoSupport__Module.html">PardisoSupport </a></td><td>Direct LLt, LDLt, LU factorizations</td><td>SPD <br  />
 SPD <br  />
 Square</td><td>Fill-in reducing, Leverage fast dense algebra, Multithreading </td><td>Requires the <a href="http://eigen.tuxfamily.org/Counter/redirect_to_mkl.php">Intel MKL</a> package, <b>Proprietary</b>  </td><td>optimized for tough problems patterns, see also <a class="el" href="TopicUsingIntelMKL.html">using MKL with Eigen </a> </td></tr>
<tr>
<td><a class="el" href="classAccelerateLLT.html" title="A direct Cholesky (LLT) factorization and solver based on Accelerate.">AccelerateLLT</a> <br  />
 <a class="el" href="classAccelerateLDLT.html" title="The default Cholesky (LDLT) factorization and solver based on Accelerate.">AccelerateLDLT</a> <br  />
 <a class="el" href="classAccelerateQR.html" title="A QR factorization and solver based on Accelerate.">AccelerateQR</a></td><td><a class="el" href="group__AccelerateSupport__Module.html">AccelerateSupport </a></td><td>Direct LLt, LDLt, QR factorizations</td><td>SPD <br  />
 SPD <br  />
 Rectangular</td><td>Fill-in reducing, Leverage fast dense algebra, Multithreading </td><td>Requires the <a href="https://developer.apple.com/documentation/accelerate">Apple Accelerate</a> package, <b>Proprietary</b>  </td><td></td></tr>
</table>
<p>Here <code>SPD</code> means symmetric positive definite.</p>
<h1><a class="anchor" id="TutorialSparseSolverConcept"></a>
Sparse solver concept</h1>
<p>All these solvers follow the same general concept. Here is a typical and general example: </p><div class="fragment"><div class="line"><span class="preprocessor">#include &lt;Eigen/RequiredModuleName&gt;</span></div>
<div class="line"><span class="comment">// ...</span></div>
<div class="line">SparseMatrix&lt;double&gt; A;</div>
<div class="line"><span class="comment">// fill A</span></div>
<div class="line"><a class="code" href="group__matrixtypedefs.html#ga8554c6170729f01c7572574837ecf618">VectorXd</a> b, x;</div>
<div class="line"><span class="comment">// fill b</span></div>
<div class="line"><span class="comment">// solve Ax = b</span></div>
<div class="line">SolverClassName&lt;SparseMatrix&lt;double&gt; &gt; solver;</div>
<div class="line">solver.compute(A);</div>
<div class="line"><span class="keywordflow">if</span>(solver.info()!=<a class="code" href="group__enums.html#gga85fad7b87587764e5cf6b513a9e0ee5ea671a2aeb0f527802806a441d58a80fcf">Success</a>) {</div>
<div class="line">  <span class="comment">// decomposition failed</span></div>
<div class="line">  <span class="keywordflow">return</span>;</div>
<div class="line">}</div>
<div class="line">x = solver.solve(b);</div>
<div class="line"><span class="keywordflow">if</span>(solver.info()!=<a class="code" href="group__enums.html#gga85fad7b87587764e5cf6b513a9e0ee5ea671a2aeb0f527802806a441d58a80fcf">Success</a>) {</div>
<div class="line">  <span class="comment">// solving failed</span></div>
<div class="line">  <span class="keywordflow">return</span>;</div>
<div class="line">}</div>
<div class="line"><span class="comment">// solve for another right hand side:</span></div>
<div class="line">x1 = solver.solve(b1);</div>
<div class="ttc" id="agroup__enums_html_gga85fad7b87587764e5cf6b513a9e0ee5ea671a2aeb0f527802806a441d58a80fcf"><div class="ttname"><a href="group__enums.html#gga85fad7b87587764e5cf6b513a9e0ee5ea671a2aeb0f527802806a441d58a80fcf">Eigen::Success</a></div><div class="ttdeci">@ Success</div><div class="ttdef"><b>Definition:</b> Constants.h:444</div></div>
<div class="ttc" id="agroup__matrixtypedefs_html_ga8554c6170729f01c7572574837ecf618"><div class="ttname"><a href="group__matrixtypedefs.html#ga8554c6170729f01c7572574837ecf618">Eigen::VectorXd</a></div><div class="ttdeci">Matrix&lt; double, Dynamic, 1 &gt; VectorXd</div><div class="ttdoc">Dynamic×1 vector of type double.</div><div class="ttdef"><b>Definition:</b> Matrix.h:501</div></div>
</div><!-- fragment --><p>For <code>SPD</code> solvers, a second optional template argument allows to specify which triangular part have to be used, e.g.:</p>
<div class="fragment"><div class="line"><span class="preprocessor">#include &lt;Eigen/IterativeLinearSolvers&gt;</span></div>
<div class="line"> </div>
<div class="line">ConjugateGradient&lt;SparseMatrix&lt;double&gt;, <a class="code" href="group__enums.html#gga39e3366ff5554d731e7dc8bb642f83cdafca2ccebb604f171656deb53e8c083c1">Eigen::Upper</a>&gt; solver;</div>
<div class="line">x = solver.compute(A).solve(b);</div>
<div class="ttc" id="agroup__enums_html_gga39e3366ff5554d731e7dc8bb642f83cdafca2ccebb604f171656deb53e8c083c1"><div class="ttname"><a href="group__enums.html#gga39e3366ff5554d731e7dc8bb642f83cdafca2ccebb604f171656deb53e8c083c1">Eigen::Upper</a></div><div class="ttdeci">@ Upper</div><div class="ttdef"><b>Definition:</b> Constants.h:213</div></div>
</div><!-- fragment --><p> In the above example, only the upper triangular part of the input matrix A is considered for solving. The opposite triangle might either be empty or contain arbitrary values.</p>
<p>In the case where multiple problems with the same sparsity pattern have to be solved, then the "compute" step can be decomposed as follow: </p><div class="fragment"><div class="line">SolverClassName&lt;SparseMatrix&lt;double&gt; &gt; solver;</div>
<div class="line">solver.analyzePattern(A);   <span class="comment">// for this step the numerical values of A are not used</span></div>
<div class="line">solver.factorize(A);</div>
<div class="line">x1 = solver.solve(b1);</div>
<div class="line">x2 = solver.solve(b2);</div>
<div class="line">...</div>
<div class="line">A = ...;                    <span class="comment">// modify the values of the nonzeros of A, the nonzeros pattern must stay unchanged</span></div>
<div class="line">solver.factorize(A);</div>
<div class="line">x1 = solver.solve(b1);</div>
<div class="line">x2 = solver.solve(b2);</div>
<div class="line">...</div>
</div><!-- fragment --><p> The <code>compute()</code> method is equivalent to calling both <code>analyzePattern()</code> and <code>factorize()</code>.</p>
<p>Each solver provides some specific features, such as determinant, access to the factors, controls of the iterations, and so on. More details are available in the documentations of the respective classes.</p>
<p>Finally, most of the iterative solvers, can also be used in a <b>matrix-free</b> context, see the following <a class="el" href="group__MatrixfreeSolverExample.html">example </a>.</p>
<h1><a class="anchor" id="TheSparseCompute"></a>
The Compute Step</h1>
<p>In the <code>compute()</code> function, the matrix is generally factorized: <a class="el" href="classEigen_1_1LLT.html" title="Standard Cholesky decomposition (LL^T) of a matrix and associated features.">LLT</a> for self-adjoint matrices, <a class="el" href="classEigen_1_1LDLT.html" title="Robust Cholesky decomposition of a matrix with pivoting.">LDLT</a> for general hermitian matrices, LU for non hermitian matrices and QR for rectangular matrices. These are the results of using direct solvers. For this class of solvers precisely, the compute step is further subdivided into <code>analyzePattern()</code> and <code>factorize()</code>.</p>
<p>The goal of <code>analyzePattern()</code> is to reorder the nonzero elements of the matrix, such that the factorization step creates less fill-in. This step exploits only the structure of the matrix. Hence, the results of this step can be used for other linear systems where the matrix has the same structure. Note however that sometimes, some external solvers (like <a class="el" href="classEigen_1_1SuperLU.html" title="A sparse direct LU factorization and solver based on the SuperLU library.">SuperLU</a>) require that the values of the matrix are set in this step, for instance to equilibrate the rows and columns of the matrix. In this situation, the results of this step should not be used with other matrices.</p>
<p><a class="el" href="namespaceEigen.html" title="Namespace containing all symbols from the Eigen library.">Eigen</a> provides a limited set of methods to reorder the matrix in this step, either built-in (COLAMD, AMD) or external (METIS). These methods are set in template parameter list of the solver : </p><div class="fragment"><div class="line">DirectSolverClassName&lt;SparseMatrix&lt;double&gt;, OrderingMethod&lt;IndexType&gt; &gt; solver;</div>
</div><!-- fragment --><p>See the <a class="el" href="group__OrderingMethods__Module.html">OrderingMethods module </a> for the list of available methods and the associated options.</p>
<p>In <code>factorize()</code>, the factors of the coefficient matrix are computed. This step should be called each time the values of the matrix change. However, the structural pattern of the matrix should not change between multiple calls.</p>
<p>For iterative solvers, the compute step is used to eventually setup a preconditioner. For instance, with the ILUT preconditioner, the incomplete factors L and U are computed in this step. Remember that, basically, the goal of the preconditioner is to speedup the convergence of an iterative method by solving a modified linear system where the coefficient matrix has more clustered eigenvalues. For real problems, an iterative solver should always be used with a preconditioner. In <a class="el" href="namespaceEigen.html" title="Namespace containing all symbols from the Eigen library.">Eigen</a>, a preconditioner is selected by simply adding it as a template parameter to the iterative solver object. </p><div class="fragment"><div class="line">IterativeSolverClassName&lt;SparseMatrix&lt;double&gt;, PreconditionerName&lt;SparseMatrix&lt;double&gt; &gt; solver; </div>
</div><!-- fragment --><p> The member function <code>preconditioner()</code> returns a read-write reference to the preconditioner to directly interact with it. See the <a class="el" href="group__IterativeLinearSolvers__Module.html">Iterative solvers module </a> and the documentation of each class for the list of available methods.</p>
<h1><a class="anchor" id="TheSparseSolve"></a>
The Solve step</h1>
<p>The <code>solve()</code> function computes the solution of the linear systems with one or many right hand sides. </p><div class="fragment"><div class="line">X = solver.solve(B);</div>
</div><!-- fragment --><p> Here, B can be a vector or a matrix where the columns form the different right hand sides. <code>The solve()</code> function can be called several times as well, for instance when all the right hand sides are not available at once. </p><div class="fragment"><div class="line">x1 = solver.solve(b1);</div>
<div class="line"><span class="comment">// Get the second right hand side b2</span></div>
<div class="line">x2 = solver.solve(b2); </div>
<div class="line"><span class="comment">//  ...</span></div>
</div><!-- fragment --><p> For direct methods, the solution are computed at the machine precision. Sometimes, the solution need not be too accurate. In this case, the iterative methods are more suitable and the desired accuracy can be set before the solve step using <b>setTolerance()</b>. For all the available functions, please, refer to the documentation of the <a class="el" href="group__IterativeLinearSolvers__Module.html">Iterative solvers module </a>.</p>
<h1><a class="anchor" id="BenchmarkRoutine"></a>
BenchmarkRoutine</h1>
<p>Most of the time, all you need is to know how much time it will take to solve your system, and hopefully, what is the most suitable solver. In <a class="el" href="namespaceEigen.html" title="Namespace containing all symbols from the Eigen library.">Eigen</a>, we provide a benchmark routine that can be used for this purpose. It is very easy to use. In the build directory, navigate to <code>bench/spbench</code> and compile the routine by typing <code>make spbenchsolver</code>. Run it with <code>--help</code> option to get the list of all available options. Basically, the matrices to test should be in <a href="http://math.nist.gov/MatrixMarket/formats.html">MatrixMarket Coordinate format</a>, and the routine returns the statistics from all available solvers in <a class="el" href="namespaceEigen.html" title="Namespace containing all symbols from the Eigen library.">Eigen</a>.</p>
<p>To export your matrices and right-hand-side vectors in the matrix-market format, you can the the unsupported SparseExtra module: </p><div class="fragment"><div class="line"><span class="preprocessor">#include &lt;unsupported/Eigen/SparseExtra&gt;</span></div>
<div class="line">...</div>
<div class="line">Eigen::saveMarket(A, <span class="stringliteral">&quot;filename.mtx&quot;</span>);</div>
<div class="line">Eigen::saveMarket(A, <span class="stringliteral">&quot;filename_SPD.mtx&quot;</span>, <a class="code" href="group__enums.html#gga39e3366ff5554d731e7dc8bb642f83cdad5381b2d1c8973a08303c94e7da02333">Eigen::Symmetric</a>); <span class="comment">// if A is symmetric-positive-definite</span></div>
<div class="line">Eigen::saveMarketVector(B, <span class="stringliteral">&quot;filename_b.mtx&quot;</span>);</div>
<div class="ttc" id="agroup__enums_html_gga39e3366ff5554d731e7dc8bb642f83cdad5381b2d1c8973a08303c94e7da02333"><div class="ttname"><a href="group__enums.html#gga39e3366ff5554d731e7dc8bb642f83cdad5381b2d1c8973a08303c94e7da02333">Eigen::Symmetric</a></div><div class="ttdeci">@ Symmetric</div><div class="ttdef"><b>Definition:</b> Constants.h:229</div></div>
</div><!-- fragment --><p>The following table gives an example of XML statistics from several <a class="el" href="namespaceEigen.html" title="Namespace containing all symbols from the Eigen library.">Eigen</a> built-in and external solvers. </p><table border="1">
<tr>
<th><a class="el" href="classEigen_1_1Matrix.html" title="The matrix class, also used for vectors and row-vectors.">Matrix</a> </th><th>N </th><th>NNZ </th><th></th><th>UMFPACK </th><th>SUPERLU </th><th>PASTIX LU </th><th><a class="el" href="classEigen_1_1BiCGSTAB.html" title="A bi conjugate gradient stabilized solver for sparse square problems.">BiCGSTAB</a> </th><th>BiCGSTAB+ILUT </th><th>GMRES+ILUT</th><th><a class="el" href="classEigen_1_1LDLT.html" title="Robust Cholesky decomposition of a matrix with pivoting.">LDLT</a> </th><th>CHOLMOD <a class="el" href="classEigen_1_1LDLT.html" title="Robust Cholesky decomposition of a matrix with pivoting.">LDLT</a> </th><th>PASTIX <a class="el" href="classEigen_1_1LDLT.html" title="Robust Cholesky decomposition of a matrix with pivoting.">LDLT</a> </th><th><a class="el" href="classEigen_1_1LLT.html" title="Standard Cholesky decomposition (LL^T) of a matrix and associated features.">LLT</a> </th><th>CHOLMOD SP <a class="el" href="classEigen_1_1LLT.html" title="Standard Cholesky decomposition (LL^T) of a matrix and associated features.">LLT</a> </th><th>CHOLMOD <a class="el" href="classEigen_1_1LLT.html" title="Standard Cholesky decomposition (LL^T) of a matrix and associated features.">LLT</a> </th><th>PASTIX <a class="el" href="classEigen_1_1LLT.html" title="Standard Cholesky decomposition (LL^T) of a matrix and associated features.">LLT</a> </th><th>CG </th></tr>
<tr>
<th rowspan="4">vector_graphics </th><td rowspan="4">12855 </td><td rowspan="4">72069 </td><th>Compute Time </th><td>0.0254549</td><td>0.0215677</td><td>0.0701827</td><td>0.000153388</td><td>0.0140107</td><td>0.0153709</td><td>0.0101601</td><td style="background-color:red">0.00930502</td><td>0.0649689 </td></tr>
<tr>
<th><a class="el" href="classEigen_1_1Solve.html" title="Pseudo expression representing a solving operation.">Solve</a> Time </th><td>0.00337835</td><td>0.000951826</td><td>0.00484373</td><td>0.0374886</td><td>0.0046445</td><td>0.00847754</td><td>0.000541813</td><td style="background-color:red">0.000293696</td><td>0.00485376 </td></tr>
<tr>
<th>Total Time </th><td>0.0288333</td><td>0.0225195</td><td>0.0750265</td><td>0.037642</td><td>0.0186552</td><td>0.0238484</td><td>0.0107019</td><td style="background-color:red">0.00959871</td><td>0.0698227 </td></tr>
<tr>
<th>Error(Iter) </th><td>1.299e-16 </td><td>2.04207e-16 </td><td>4.83393e-15 </td><td>3.94856e-11 (80) </td><td>1.03861e-12 (3) </td><td>5.81088e-14 (6) </td><td>1.97578e-16 </td><td>1.83927e-16 </td><td>4.24115e-15 </td></tr>
<tr>
<th rowspan="4">poisson_SPD </th><td rowspan="4">19788 </td><td rowspan="4">308232 </td><th>Compute Time </th><td>0.425026</td><td>1.82378</td><td>0.617367</td><td>0.000478921</td><td>1.34001</td><td>1.33471</td><td>0.796419</td><td>0.857573</td><td>0.473007</td><td>0.814826</td><td style="background-color:red">0.184719</td><td>0.861555</td><td>0.470559</td><td>0.000458188 </td></tr>
<tr>
<th><a class="el" href="classEigen_1_1Solve.html" title="Pseudo expression representing a solving operation.">Solve</a> Time </th><td>0.0280053</td><td>0.0194402</td><td>0.0268747</td><td>0.249437</td><td>0.0548444</td><td>0.0926991</td><td>0.00850204</td><td>0.0053171</td><td>0.0258932</td><td>0.00874603</td><td style="background-color:red">0.00578155</td><td>0.00530361</td><td>0.0248942</td><td>0.239093 </td></tr>
<tr>
<th>Total Time </th><td>0.453031</td><td>1.84322</td><td>0.644241</td><td>0.249916</td><td>1.39486</td><td>1.42741</td><td>0.804921</td><td>0.862891</td><td>0.4989</td><td>0.823572</td><td style="background-color:red">0.190501</td><td>0.866859</td><td>0.495453</td><td>0.239551 </td></tr>
<tr>
<th>Error(Iter) </th><td>4.67146e-16 </td><td>1.068e-15 </td><td>1.3397e-15 </td><td>6.29233e-11 (201) </td><td>3.68527e-11 (6) </td><td>3.3168e-15 (16) </td><td>1.86376e-15 </td><td>1.31518e-16 </td><td>1.42593e-15 </td><td>3.45361e-15 </td><td>3.14575e-16 </td><td>2.21723e-15 </td><td>7.21058e-16 </td><td>9.06435e-12 (261) </td></tr>
<tr>
<th rowspan="4">sherman2 </th><td rowspan="4">1080 </td><td rowspan="4">23094 </td><th>Compute Time </th><td style="background-color:red">0.00631754</td><td>0.015052</td><td>0.0247514 </td><td>-</td><td>0.0214425</td><td>0.0217988 </td></tr>
<tr>
<th><a class="el" href="classEigen_1_1Solve.html" title="Pseudo expression representing a solving operation.">Solve</a> Time </th><td style="background-color:red">0.000478424</td><td>0.000337998</td><td>0.0010291 </td><td>-</td><td>0.00243152</td><td>0.00246152 </td></tr>
<tr>
<th>Total Time </th><td style="background-color:red">0.00679597</td><td>0.01539</td><td>0.0257805 </td><td>-</td><td>0.023874</td><td>0.0242603 </td></tr>
<tr>
<th>Error(Iter) </th><td>1.83099e-15 </td><td>8.19351e-15 </td><td>2.625e-14 </td><td>1.3678e+69 (1080) </td><td>4.1911e-12 (7) </td><td>5.0299e-13 (12) </td></tr>
<tr>
<th rowspan="4">bcsstk01_SPD </th><td rowspan="4">48 </td><td rowspan="4">400 </td><th>Compute Time </th><td>0.000169079</td><td>0.00010789</td><td>0.000572538</td><td>1.425e-06</td><td>9.1612e-05</td><td>8.3985e-05</td><td style="background-color:red">5.6489e-05</td><td>7.0913e-05</td><td>0.000468251</td><td>5.7389e-05</td><td>8.0212e-05</td><td>5.8394e-05</td><td>0.000463017</td><td>1.333e-06 </td></tr>
<tr>
<th><a class="el" href="classEigen_1_1Solve.html" title="Pseudo expression representing a solving operation.">Solve</a> Time </th><td>1.2288e-05</td><td>1.1124e-05</td><td>0.000286387</td><td>8.5896e-05</td><td>1.6381e-05</td><td>1.6984e-05</td><td style="background-color:red">3.095e-06</td><td>4.115e-06</td><td>0.000325438</td><td>3.504e-06</td><td>7.369e-06</td><td>3.454e-06</td><td>0.000294095</td><td>6.0516e-05 </td></tr>
<tr>
<th>Total Time </th><td>0.000181367</td><td>0.000119014</td><td>0.000858925</td><td>8.7321e-05</td><td>0.000107993</td><td>0.000100969</td><td style="background-color:red">5.9584e-05</td><td>7.5028e-05</td><td>0.000793689</td><td>6.0893e-05</td><td>8.7581e-05</td><td>6.1848e-05</td><td>0.000757112</td><td>6.1849e-05 </td></tr>
<tr>
<th>Error(Iter) </th><td>1.03474e-16 </td><td>2.23046e-16 </td><td>2.01273e-16 </td><td>4.87455e-07 (48) </td><td>1.03553e-16 (2) </td><td>3.55965e-16 (2) </td><td>2.48189e-16 </td><td>1.88808e-16 </td><td>1.97976e-16 </td><td>2.37248e-16 </td><td>1.82701e-16 </td><td>2.71474e-16 </td><td>2.11322e-16 </td><td>3.547e-09 (48) </td></tr>
<tr>
<th rowspan="4">sherman1 </th><td rowspan="4">1000 </td><td rowspan="4">3750 </td><th>Compute Time </th><td>0.00228805</td><td>0.00209231</td><td>0.00528268</td><td>9.846e-06</td><td>0.00163522</td><td>0.00162155</td><td>0.000789259</td><td style="background-color:red">0.000804495</td><td>0.00438269 </td></tr>
<tr>
<th><a class="el" href="classEigen_1_1Solve.html" title="Pseudo expression representing a solving operation.">Solve</a> Time </th><td>0.000213788</td><td>9.7983e-05</td><td>0.000938831</td><td>0.00629835</td><td>0.000361764</td><td>0.00078794</td><td>4.3989e-05</td><td style="background-color:red">2.5331e-05</td><td>0.000917166 </td></tr>
<tr>
<th>Total Time </th><td>0.00250184</td><td>0.00219029</td><td>0.00622151</td><td>0.0063082</td><td>0.00199698</td><td>0.00240949</td><td>0.000833248</td><td style="background-color:red">0.000829826</td><td>0.00529986 </td></tr>
<tr>
<th>Error(Iter) </th><td>1.16839e-16 </td><td>2.25968e-16 </td><td>2.59116e-16 </td><td>3.76779e-11 (248) </td><td>4.13343e-11 (4) </td><td>2.22347e-14 (10) </td><td>2.05861e-16 </td><td>1.83555e-16 </td><td>1.02917e-15 </td></tr>
<tr>
<th rowspan="4">young1c </th><td rowspan="4">841 </td><td rowspan="4">4089 </td><th>Compute Time </th><td>0.00235843</td><td style="background-color:red">0.00217228</td><td>0.00568075</td><td>1.2735e-05</td><td>0.00264866</td><td>0.00258236 </td></tr>
<tr>
<th><a class="el" href="classEigen_1_1Solve.html" title="Pseudo expression representing a solving operation.">Solve</a> Time </th><td>0.000329599</td><td style="background-color:red">0.000168634</td><td>0.00080118</td><td>0.0534738</td><td>0.00187193</td><td>0.00450211 </td></tr>
<tr>
<th>Total Time </th><td>0.00268803</td><td style="background-color:red">0.00234091</td><td>0.00648193</td><td>0.0534865</td><td>0.00452059</td><td>0.00708447 </td></tr>
<tr>
<th>Error(Iter) </th><td>1.27029e-16 </td><td>2.81321e-16 </td><td>5.0492e-15 </td><td>8.0507e-11 (706) </td><td>3.00447e-12 (8) </td><td>1.46532e-12 (16) </td></tr>
<tr>
<th rowspan="4">mhd1280b </th><td rowspan="4">1280 </td><td rowspan="4">22778 </td><th>Compute Time </th><td>0.00234898</td><td>0.00207079</td><td>0.00570918</td><td>2.5976e-05</td><td>0.00302563</td><td>0.00298036</td><td>0.00144525</td><td style="background-color:red">0.000919922</td><td>0.00426444 </td></tr>
<tr>
<th><a class="el" href="classEigen_1_1Solve.html" title="Pseudo expression representing a solving operation.">Solve</a> Time </th><td>0.00103392</td><td>0.000211911</td><td>0.00105</td><td>0.0110432</td><td>0.000628287</td><td>0.00392089</td><td>0.000138303</td><td style="background-color:red">6.2446e-05</td><td>0.00097564 </td></tr>
<tr>
<th>Total Time </th><td>0.0033829</td><td>0.0022827</td><td>0.00675918</td><td>0.0110692</td><td>0.00365392</td><td>0.00690124</td><td>0.00158355</td><td style="background-color:red">0.000982368</td><td>0.00524008 </td></tr>
<tr>
<th>Error(Iter) </th><td>1.32953e-16 </td><td>3.08646e-16 </td><td>6.734e-16 </td><td>8.83132e-11 (40) </td><td>1.51153e-16 (1) </td><td>6.08556e-16 (8) </td><td>1.89264e-16 </td><td>1.97477e-16 </td><td>6.68126e-09 </td></tr>
<tr>
<th rowspan="4">crashbasis </th><td rowspan="4">160000 </td><td rowspan="4">1750416 </td><th>Compute Time </th><td>3.2019</td><td>5.7892</td><td>15.7573</td><td style="background-color:red">0.00383515</td><td>3.1006</td><td>3.09921 </td></tr>
<tr>
<th><a class="el" href="classEigen_1_1Solve.html" title="Pseudo expression representing a solving operation.">Solve</a> Time </th><td>0.261915</td><td>0.106225</td><td>0.402141</td><td style="background-color:red">1.49089</td><td>0.24888</td><td>0.443673 </td></tr>
<tr>
<th>Total Time </th><td>3.46381</td><td>5.89542</td><td>16.1594</td><td style="background-color:red">1.49473</td><td>3.34948</td><td>3.54288 </td></tr>
<tr>
<th>Error(Iter) </th><td>1.76348e-16 </td><td>4.58395e-16 </td><td>1.67982e-14 </td><td>8.64144e-11 (61) </td><td>8.5996e-12 (2) </td><td><p class="starttd">6.04042e-14 (5)</p>
<p class="endtd"></p>
</td></tr>
</table>
</div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
  <ul>
    <li class="footer">Generated on Thu Apr 21 2022 13:07:55 for Eigen by
    <a href="http://www.doxygen.org/index.html">
    <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.9.1 </li>
  </ul>
</div>
</body>
</html>
